Many telecommunications network service providers, cable TV operators, and telecommunications equipment providers are showing significant interest in provisioning content distribution services such as Video-on-Demand (VOD). Primary application areas include on-demand home entertainment, remote learning and training, video conferencing, and news-on-demand. These services are expected to grow significantly over time and become an important source of income for the service providers. However, in order to provide adequate service, significant bandwidth resources must be available, which implies large capital investment. For example, in near-VOD applications a server may broadcast a copy of a popular movie every five minutes which implies that a customer may wait, on average, 2.5 minutes. Thus, if the length of the movie is 100 minutes, the network would carry simultaneously 20 copies of the movie, which would require significant bandwidth resources. The available bandwidth resources in the network will dictate the service provided in near-VOD applications in terms of the waiting time for customers for the next copy of the movie. In other delivery technologies that provide almost instantaneous VOD delivery, bandwidth allocation to any program can be controlled by changing the video quality provided to users. The quality expected by customers may depend on the application. For example, broadcasting of movies requires better video quality than multicasting of video conferences.
Consider a tree network with directed links where the root node of the tree has a server that stores and broadcasts multiple programs to serve requests for programs at multiple nodes of the tree. Since the bandwidth capacity of each link is limited, prudent allocation of bandwidth is needed in order to serve adequately all requested programs at the various nodes. In particular, it is important to achieve an equitable allocation of bandwidth among the various programs along all links of the tree network. This is a challenging objective since the bandwidth allocated on a link for a specific program may decrease from one link to the next in a path from the root node to an end-node, but may not increase.
Several methods that allocate the bandwidth in a tree network have been published. S. Sarkar and L. Tassiulas, Distributed Algorithms for Computation of Fair Rates in Multirate Multicast Trees, Proceedings of IEEE INFOCOM 2000, 52-62, Tel Aviv, March, 2000 propose a method for equitable allocation along the links of the tree for linear performance functions, representing throughput. S. Sarkar and L. Tassiulas, Fair Bandwidth Allocation for Multicasting in Networks with Discrete Feasible Set, IEEE Transactions on Computers 53, 785-797, 2004 extend the model to discrete bandwidth allocation. The extended model is an NP-complete problem and the authors provided an algorithm for a simplified objective function that approximates an equitable solution. C. Y. Lee, Y. P. Moon, and Y. J. Cho, A Lexicographically Fair Allocation of Discrete Bandwidth for Multirate Multicast Traffics, Computers and Operations Research 31, 2349-2363, 2004 and C. Y. Lee and H. K. Cho, Discrete Bandwidth Allocation Considering Fairness and Transmission load in Multicast Networks, Computers and Operations Research 34, 884-899, 2007 also provide algorithms for the discrete allocation case. They provide heuristics to an objective function that approximates equitable solutions. All the references above present algorithms limited to finding equitable throughput. These algorithms use bandwidth allocated to source-destination (also referred to as “virtual sessions”) as decision variables
H. Luss, An Equitable Bandwidth Allocation Model for Video-on-Demand Networks, Networks and Spatial Economics. 8, 23-41, 2008. (Also, H. Luss, “Bandwidth Allocation for Video-on-Demand Networks”, U.S. Pat. No. 7,664,020) presents an algorithm for the same equitable bandwidth allocation problem, but which is formulated differently. The decision variables are the bandwidth allocations to the programs on a link (regardless of the destination). The decision variables for each program must satisfy tree-like ordering constraints that ensure, for each program, that the bandwidth allocated cannot increase from one link to the next when moving farther away from the root node. The model assumes general performance functions for each program (continuous, strictly increasing, but not necessarily linearly) that may also depend on the receiving node. Nonlinear performance functions are important since they may, for example, represent diminishing rates of increase in satisfaction when the provided bandwidth is increased.
H. Luss, Equitable Bandwidth Allocation in Content Distribution Networks, Naval Research Logistics, published on-line, DOI 10.1002/nav.20400, January 2010 (also, H. Luss, “Method for Equitable Bandwidth Allocation for Content Distribution Networks”, U.S. Patent Application Publication No. 2009/0213875) assumes that the performance functions may depend on the program, but for any specific program they are the same at all nodes. Luss provides an algorithm which results in an optimal solution in polynomial time for linear and for certain nonlinear performance functions. The algorithm can be used for even more general performance functions though the computation time then depends on the required accuracy of the solution.
Note that in some of the references, the underlying problem is described in terms of multiple multicasting sessions, while other references describe the underlying problem as broadcasting of multiple programs. Nevertheless, these problems are essentially the same.
In the present invention the algorithm in the last mentioned reference (Luss 2010) is extended to a distributed environment where the intensive computations are done at each of the nodes independently while only minimal information is exchanged among the nodes. A distributed method is attractive as it eliminates the need for a central computing device. It also facilitates very quick adaptation to changes over time, such as introduction of new programs and deletion of existing programs.